//
// Created by Administrator on 2021/8/20.
//
//给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。
//
//如果剩余字符少于 k 个，则将剩余字符全部反转。
//如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
//
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/reverse-string-ii
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    string reverseStr(string s, int k) {
        // 找到需要交换的两端
        for (int i = 0; i < s.size(); i += 2 * k) {
            if (i + k < s.size())
                reverse(s, i, i + k - 1);
            else
                reverse(s, i, (int) s.size() - 1);
        }
        return s;
    }

    void reverse(string &s, int left, int right) {
        while (left < right) {
            swap(s[left], s[right]);
            ++left;
            --right;
        }
    }
};

class Solution2 { // 题解
public:
    string reverseStr(string s, int k) {
        int n = (int) s.length();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(s.begin() + i, s.begin() + min(i + k, n)); // reverse 左闭右开
        }
        return s;
    }
};

int main() {
    Solution solution;
    cout << solution.reverseStr("leetcode", 4) << endl;
    cout << solution.reverseStr("abcdefg", 2) << endl;
    cout << solution.reverseStr("abcd", 2) << endl;
    return 0;
}
